package com.ssh;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import org.junit.Test;

public class ThreeSum_15 {
	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);
		int s = 0;
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for (int i = 0; i < nums.length; i++) {
			for (int j = i+1; j < nums.length; j++) {
				s = nums[i] + nums[j];
				for (int z = j+1; z < nums.length; z++) {
					if (-s == nums[z]) {
						List<Integer> l = new ArrayList<Integer>();
						l.add(nums[i]);
						l.add(nums[j]);
						l.add(nums[z]);
						if (!list.contains(l)) {
							list.add(l);
						}
						break;
					}
				}
			}
		}
		return list;
    }
	
	public List<List<Integer>> threeSum1(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for (int i =0; i < nums.length-2; i++) {
			if (i == 0 || (nums[i] != nums[i-1])) {
				int lo = i+1,hi = nums.length-1,sum = 0-nums[i];
				while (lo < hi) {
					if (nums[lo] + nums[hi] == sum) {
						list.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
						while (lo < hi && nums[lo] == nums[lo+1]) {
							lo++;
						}
						while (lo < hi && nums[hi] == nums[hi-1]) {
							hi--;
						}
						lo++;hi--;
					}else if (nums[lo] + nums[hi] < sum) {
						lo++;
					}else {
						hi--;
					}
				}
			}
		}
		return list;
	}
	@Test
	public void test () {
		int[] nums = {-1,0,1,2,-1,-4};
		System.out.println(threeSum1(nums));
	}
}
